grammar Checker;

options {
    backtrack=true;
    memoize=true;
}

@lexer::members {
	public void displayRecognitionError(String[] tokenNames, RecognitionException err) {
	
	}
}

check returns [String s] 
	: BUBBLE {s = "Bubble sort";}
	| GNOME {s = "Gnome sort";}
	| SHAKER {s = "Shaker sort";}
	| SELECTION {s = "Selection sort";}
	| INSERTION {s = "Insertion sort";}
	| SHELL {s = "Shell sort";}
	| HEAP {s = "Heap sort";}
	| MERGE {s = "Merge sort";}
	| QUICK {s = "Quick sort";}
	| OTHERS {s = "False";}
	| EOF {s = "False";}
	;

BUBBLE : '(2,0)(3,1)(1,0)(2,2)(0,0)(1,3)(2,1)(3,2)(1,1)(2,3)(2,2)(3,3)'
		| '(3,1)(2,0)(2,2)(1,0)(1,3)(0,0)(3,2)(2,1)(2,3)(1,1)(3,3)(2,2)'
		| '(0,2)(1,3)(1,1)(2,3)(2,0)(3,3)(0,1)(1,2)(1,0)(2,2)(0,0)(1,1)'
		| '(1,3)(0,2)(2,3)(1,1)(3,3)(2,0)(1,2)(0,1)(2,2)(1,0)(1,1)(0,0)'
		;
		
GNOME : '(1,3)(0,2)(2,3)(1,1)(1,2)(0,1)(3,3)(2,0)(2,2)(1,0)(1,1)(0,0)'
	| '(0,2)(1,3)(1,1)(2,3)(0,1)(1,2)(2,0)(3,3)(1,0)(2,2)(0,0)(1,1)'
	| '(2,0)(3,1)(1,0)(2,2)(2,1)(3,2)(0,0)(1,3)(1,1)(2,3)(2,2)(3,3)'
	| '(3,1)(2,0)(2,2)(1,0)(3,2)(2,1)(1,3)(0,0)(2,3)(1,1)(3,3)(2,2)'
	;
	
SHAKER : '(0,2)(1,3)(1,1)(2,3)(2,0)(3,3)(2,1)(1,0)(1,2)(0,0)(1,1)(2,2)'
	| '(1,3)(0,2)(2,3)(1,1)(3,3)(2,0)(2,1)(1,0)(1,2)(0,0)(2,2)(1,1)'
	| '(0,2)(1,3)(1,1)(2,3)(2,0)(3,3)(1,0)(2,1)(0,0)(1,2)(1,1)(2,2)'
	| '(1,3)(0,2)(2,3)(1,1)(3,3)(2,0)(1,0)(2,1)(0,0)(1,2)(2,2)(1,1)'
	| '(2,0)(3,1)(1,0)(2,2)(0,0)(1,3)(2,3)(1,2)(3,3)(2,1)(1,1)(2,2)'
	| '(3,1)(2,0)(2,2)(1,0)(1,3)(0,0)(2,3)(1,2)(3,3)(2,1)(2,2)(1,1)'
	| '(2,0)(3,1)(1,0)(2,2)(0,0)(1,3)(1,2)(2,3)(2,1)(3,3)(1,1)(2,2)'
	| '(3,1)(2,0)(2,2)(1,0)(1,3)(0,0)(1,2)(2,3)(2,1)(3,3)(2,2)(1,1)'
	;
		
SELECTION : '(0,0)(3,3)(1,1)(2,2)(2,2)(2,2)(3,3)(3,3)'
		| '(3,3)(0,0)(2,2)(1,1)(2,2)(2,2)(3,3)(3,3)'
		| '(0,0)(3,3)(1,1)(2,2)(1,1)(1,1)(0,0)(0,0)'
		| '(3,3)(0,0)(2,2)(1,1)(1,1)(1,1)(0,0)(0,0)'
		| '(0,0)(3,3)(1,1)(2,2)(2,2)(2,2)'
		| '(3,3)(0,0)(2,2)(1,1)(2,2)(2,2)'
		| '(0,0)(3,3)(1,1)(2,2)(1,1)(1,1)'
		| '(3,3)(0,0)(2,2)(1,1)(1,1)(1,1)'
		| '(0,0)(3,3)(1,1)(2,2)'
		| '(3,3)(0,0)(2,2)(1,1)'
		;
		
INSERTION : '(1,3)(0,2)(2,3)(1,2)(0,1)(3,3)(2,2)(1,1)(0,0)'
		| '(2,0)(3,1)(1,0)(2,1)(3,2)(0,0)(1,1)(2,2)(3,3)'
		;

SHELL : '(2,3)(0,1)(3,2)(1,0)(1,1)(0,0)(3,3)(2,2)'
	| '(1,0)(3,2)(0,1)(2,3)(2,2)(3,3)(0,0)(1,1)'
	;

HEAP : '(0,0)(3,3)(0,2)(1,0)(0,1)(2,2)(0,0)(1,1)'
	| '(0,0)(3,3)(1,0)(0,2)(0,1)(2,2)(0,0)(1,1)'
	| '(3,3)(0,0)(0,2)(1,0)(2,2)(0,1)(1,1)(0,0)'
	| '(3,3)(0,0)(1,0)(0,2)(2,2)(0,1)(1,1)(0,0)'
	;

MERGE : '(0,2)(1,3)(2,0)(3,1)(0,0)(1,1)(2,2)(3,3)'
	| '(2,0)(3,1)(0,2)(1,3)(0,0)(1,1)(2,2)(3,3)'
	| '(1,3)(0,2)(3,1)(2,0)(3,3)(2,2)(1,1)(0,0)'
	| '(3,1)(2,0)(1,3)(0,2)(3,3)(2,2)(1,1)(0,0)'
	;

QUICK : '(0,0)(3,3)(0,0)(0,0)(1,1)(2,2)'
	| '(3,3)(0,0)(0,0)(0,0)(2,2)(1,1)'
	| '(0,0)(3,3)(3,3)(3,3)(1,1)(2,2)'
	| '(3,3)(0,0)(3,3)(3,3)(2,2)(1,1)'
	;
		
OTHERS : .;
